A. Field of the Invention
The present invention relates generally to arbitration, and more particularly, to a high-speed round robin arbitration scheme.
B. Description of Related Art
Routers receive data on a physical media, such as optical fiber, analyze the data to determine its destination, and output the data on a physical media in accordance with the destination. Routers were initially designed using a general purpose processor executing large software programs. As line rates and traffic volume increased, however, general purpose processors could not scale to meet these new demands. For example, as functionality was added to the software, such as accounting and policing functionality, these routers suffered performance degradation. In some instances, the routers failed to handle traffic at line rate when the new functionality was enabled.
To meet the new demands, purpose-built routers were designed. Purpose-built routers are designed and built with components optimized for routing. They not only handle higher line rates and higher network traffic volume, they also add functionality without compromising line rate performance.
A purpose-built router may include a number of input and output ports from which it transmits and receives information packets. A switching fabric may be implemented in the router to carry the packets between ports.
One function that may be implemented within a purpose-built router is the arbitration of data as it passes through various components of the router. For example, information packets from a number of different sources may be temporarily stored in a corresponding number of queues. The packets in the queues may be chosen for processing in an order determined by an arbiter, such as a round robin arbiter.
Conventionally, round robin arbiters operate by sequentially cycling through each possible requester, such as the requesting queues, and checking whether the active requester in the cycle has data to be serviced. Queues that are not active may be skipped by the round robin arbiter. If so, the round robin arbiter initiates service on the active requester. In the situation given above, for example, in which a round robin arbiter arbitrates among multiple queues, if an active queue has a packet ready to be serviced, the round robin arbiter may initiate reading the packet from the active queue. In this manner, because the round robin arbiter sequentially cycles through each requester, the round robin arbiter gives equal priority to each requester.
Purpose-built routers may have high data throughput rates, thus requiring high performance arbiters. Conventionally, as the number of possible requesters increases, the complexity of conventional implementations of an arbiter such as a round robin arbiter also increases. In some cases, the round robin arbiter may not be able to keep up with the requesters.
Accordingly, there is a need in the art to implement an efficient round robin arbiter that is able to operate at high throughput rates.